package com.zrf.base.knowledge.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * //给出一个区间的集合，请合并所有重叠的区间。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * // 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
 * //输出: [[1,6],[8,10],[15,18]]
 * //解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * //
 * //
 * // 示例 2:
 * //
 * // 输入: intervals = [[1,4],[4,5]]
 * //输出: [[1,5]]
 * //解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
 * //
 * // 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // intervals[i][0] <= intervals[i][1]
 * //
 * // Related Topics 排序 数组
 * // 👍 695 👎 0
 *
 * @author zhouruifeng
 * @date 2020-11-13 07:44:09
 */
public class MergeIntervals {
    public static void main(String[] args) {
        Solution solution = new MergeIntervals().new Solution();
        int[][] intervals  = new int[][]{
                new int[]{1,3},
                new int[]{2,6},
                new int[]{8,10},
                new int[]{15,18}
        };
        int[][] merge = solution.merge(intervals);
        System.out.println(merge);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] merge(int[][] intervals) {
            Arrays.sort(intervals, (o1, o2)-> {
                if (o1[0] == o2[0]) {
                    return 0;

                }
                return o1[0] > o2[0] ? 1 : -1;
            });

            List<int[]> resultList = new ArrayList<>();
            for (int[] interval : intervals) {
                int left = interval[0];
                int right = interval[1];

                if (resultList.isEmpty()) {
                    resultList.add(interval);
                } else {
                    int[] latest = resultList.get(resultList.size() - 1);
                    if (latest[1] < left) {
                        resultList.add(interval);
                    } else {
                        latest[1] = Math.max(latest[1], right);
                    }
                }
            }
            return resultList.toArray(new int[resultList.size()][]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}